#include <iostream>
#include <string>

int longges_common_substring(const std::string &str1, const std::string &str2, std::string &sub)
{
    int len1 = str1.size();
    int len2 = str2.size();
    int *prev = new int[len1 + 1];
    int *cur  = new int[len2 + 1];

    int maxlen = 0;
    int maxpos = 0;

    for (int k = 0; k <= len2; ++k) {
        prev[k] = 0;
    }

    for (int i = 1; i <= len1; ++i) {
        for (int j = 1; j <= len2; ++j) {
            if (str1[i-1] == str2[j-1]) {
                cur[j] = prev[j-1] + 1;

                if (cur[j] > maxlen) {
                    maxlen = cur[j];
                    maxpos = j-1;
                }
            } else {
                cur[j] = 0;
            }
        }

        for (int k = 0; k <= len2; ++k) {
            prev[k] = cur[k];
        }
    }

    sub = str2.substr(maxpos - maxlen + 1, maxlen);
    return maxlen;
}

int main(int argc, const char *argv[])
{
    std::string str1 = "abcd12345ed125ss123456789";
    std::string str2 = "jlsdg234lj91923abcd55433";
    std::string sub;
    int len = longges_common_substring(str1, str2, sub);
    std::cout << len << " " << sub << std::endl;
    return 0;
}
